class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode parent;
    public int bf; //平衡因子  右子树的高度减去左子树的高度

    public TreeNode(int val) {
        this.val = val;
    }
}

public class AVLTree {

    public TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }

        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.val > val) {
                prev = cur;
                cur = cur.left;
            } else if(cur.val < val) {
                prev = cur;
                cur = cur.right;
            } else {
                //相同的 val，直接返回
                return false;
            }
        }

        //插入结点
        if(prev.val > val) {
            prev.left = node;
        } else {
            prev.right = node;
        }
        node.parent = prev;

        cur = node;

        //调整平衡因子和AVLTree
        while(prev != null) {
            //调整平衡因子
            if(cur == prev.left) {
                prev.bf--;
            } else {
                prev.bf++;
            }

            if(prev.bf == 0) {
                //说明该树本身已经平衡，无需调节，直接退出
                break;
            } else if(prev.bf == -1 || prev.bf == 1) {
                //说明平衡因子出现变化，需要继续向上重新调整上面结点的平衡因子
                cur = prev.parent;
                prev = cur.parent;
            } else {
                //说明 AVL树 出现不平衡，需要旋转调整
                if(prev.bf == -2) { //说明左子树过高
                    //平衡因子为 -2
                    if(cur.bf == -1) { // 左左型，进行右单旋
                        rotateRight(prev);
                    } else {   //左右型，进行左右双旋
                        rotateLR(prev);
                    }
                } else {
                    //平衡因子为2 —— 说明右子树过高
                    if(cur.bf == 1) {   //右右型，进行左旋
                        rotateLeft(prev);
                    } else {     //右左型，进行右左双旋
                        rotateRL(prev);
                    }
                }

                break;//经过旋转调整，AVL 树已经平衡，直接退出循环。
            }
        }

        return true;
    }

    //右单旋
    private void rotateRight(TreeNode parent) {
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.left;

        parent.left = cur.right;
        if(cur.right != null) {
            cur.right.parent = parent;
        }
        cur.right = parent;
        parent.parent = cur;
        cur.parent = pParent;

        if(parent == root) {
            root = cur;
        } else if(pParent.left == parent) {
            pParent.left = cur;
        } else {
            pParent.right = cur;
        }

        //重新调整平衡因子
        cur.bf = parent.bf = 0;
    }

    //左单旋
    private void rotateLeft(TreeNode parent) {
        TreeNode pParent = parent.parent;
        TreeNode cur = parent.right;

        parent.right = cur.left;
        if(cur.left != null) {
            cur.left.parent = parent;
        }
        cur.left = parent;
        cur.parent = pParent;
        parent.parent = cur;

        if(parent == root) {
            root = cur;
        } else if(pParent.left == parent) {
            pParent.left = cur;
        } else {
            pParent.right = cur;
        }

        //重新调整平衡因子
        cur.bf = parent.bf = 0;
    }

    //左右双旋
    private void rotateLR(TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        int bf = curR.bf;

        rotateLeft(cur);
        rotateRight(parent);

        //重新调整平衡因子
        if(bf == 1) {
            parent.bf = -1;
        } else if(bf == -1){
            cur.bf = 1;
        }

        //当 bf = 0时，不需要修改，因为在左单旋和右旋中，三个结点的平衡因子已经变为 0，这也是为什么上面需要保存curR.bf
    }

    //右左双旋
    private void rotateRL(TreeNode parent) {
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        int bf = curL.bf;

        rotateRight(cur);
        rotateLeft(parent);

        //重新调整平衡因子
        if(bf == 1) {
            parent.bf = 1;
        } else if(bf == -1){
            cur.bf = 1;
        }

        //当 bf = 0时，不需要修改，因为在左单旋和右旋中，三个结点的平衡因子已经变为 0，这也是为什么上面需要保存curR.bf
    }

}
